from functools import cache

'''
思路

* if maxChoosableInteger >= desiredTotal:
    先出手的直接选择大于等于desiredTotal的数字即稳赢
    return True
* if sum < desiredTotal:
    谁都不可能赢
    return False
* if  sum == desiredTotal:
    最后取数的人赢
    if maxChoosableInteger % 2 == 1: 
        奇数则先出手的人赢
        return True
    else：
        偶数则后出手的人赢
        return False
* if maxChoosableInteger < desiredTotal < sum :
    - 如果能在未选择的数字中选出一个 i，使得 i +  currentTotal  ≥ desiredTotal，则能获胜， 否则继续选择
    - 如果在未选择的数字中选出一个 i，使得接下来对方无法获胜，则自己获胜
    

'''

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        @cache
        def dfs(usedNumbers: int, currentTotal: int) -> bool:
            for i in range(maxChoosableInteger):
                if (usedNumbers >> i) & 1 == 0:
                    if currentTotal + i + 1 >= desiredTotal or not dfs(usedNumbers | (1 << i), currentTotal + i + 1):
                        return True
            return False

        return (1 + maxChoosableInteger) * maxChoosableInteger // 2 >= desiredTotal and dfs(0, 0)
